package tree.binarysearchtree;

import tree.TreeNode;

/**
 * @Classname : LowestCommonAncestorOfABinarySearchTree
 * @Description :
 * <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/">235. 二叉搜索树的最近公共祖先</a>
 * @Author : chentianyu
 * @Date 2023/1/22 09:22
 */


public class LowestCommonAncestorOfABinarySearchTree {

    /**
     * 当前节点值小于二者最小值，递归到右节点
     * 当前节点值大于二者最大值，递归到左节点
     * 否则返回当前节点
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;

        if (root.val < Math.min(p.val, q.val)) return lowestCommonAncestor(root.right, p, q);
        if (root.val > Math.max(p.val, q.val)) return lowestCommonAncestor(root.left, p, q);
        return root;
    }
}
